/*
 * CS340 fatboys
 */
package fatboy.hypeerweb;

import java.io.Serializable;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.List;
import java.util.Random;

import junit.framework.AssertionFailedError;

import org.junit.Assert;
/**
 * used to keep track of addresses of nodes.  Also allows for operations to make
 *  Node operations easy.  It is a glorified int.
 *  @domain Integer >= 0.  A node address with the max integer value is a "bogus" node. 
 *      A node address with the max integer value - 1 is a "null" node.
 */
public class NodeAddress implements Serializable, Comparable<NodeAddress> {
	private static final int SIXTEEN = 16;

	private static final int SIXTY_FOUR = 64;

	private static final int Hundred = 100;

	private static final long serialVersionUID = 9152971090282999999L;	
	
	private int address;
	/**
	 * accessor method to run private test methods
	 */
	public void testNodeAddresspahse2a(){
		testConstructor();
		this.testAddOne();
		this.testDecrement();
		this.testMidPoint();
		this.testAsInt();
		testGetChild();
		this.testOnPathTo();
		this.testToString();
		this.testIsValidNeighbor();
	}
	
	/** 
	 * first of my white box test cases tests invalid input to constructor and boundary values
	 * and tests different ways of calling constructor
	 */
	/* the equivalence classes i found where 
	 * valid input >=0 and invalid <0
	 */
	public void testConstructor(){
		//tests that for negative values it doesn't work(lower boundary off by one check)
		try{
			NodeAddress bad = new NodeAddress(-1);
			Assert.fail();
		} catch(IllegalArgumentException e){	
		}
		//tests that for negative values it doesn't work checks invalid path
		try{
			NodeAddress bad = new NodeAddress(-1*Hundred);
			Assert.fail();
		} catch(IllegalArgumentException e){	
		}
		// checks for equal to smallest valid plus one a middle value and upper boundary check
		// will fail if a exception is thrown
		//checks valid path
		NodeAddress good = new NodeAddress(0);
		good = new NodeAddress(1);
		good = new NodeAddress(Integer.MAX_VALUE);
		good = new NodeAddress(Hundred);
		//makes sure that the NodeAddress.toAddress method returns a proper address
		//checks valid path, invalid path already checked above
		NodeAddress good2 = NodeAddress.toAddress(Hundred);
		Assert.assertTrue(good2.equals(good));
	}
	/**
	 * @precondition true
	 * @postcondition returns the integer representation of this nodeAddress
	 */
	public int getAddress(){
		return address;
	}

	/**
	 * @precondition incoming address is > 0
	 * @postcondition changes this nodeAddress's integer representation to address  
	 */
	private void setAddress(int address) {
		if(address < 0){
			throw new IllegalArgumentException("no neagitve addresses");
		}
		this.address = address;
	}
	
	/**
	 * @precondition incoming address is > 0
	 * @postcondition returns a new NodeAddress with the incoming address
	 */
	public NodeAddress(int address){
		setAddress(address);
	}
	
	/**
	 * takes this Address and adds one to it then returns the new address
	 * @precondition the NodeAddress this is called on is not at the maximum allowed address
	 * @postcondition returns a new NodeAddres with an address one greater than this ones.
	 */
	public NodeAddress addOne(){
		
		return new NodeAddress(address+1);
	}
	/**
	 * tests all possible paths through addOne and the only invalid input;
	 */
	// Equivalence partitions are  0<= address < max or address == max 
	public void testAddOne(){
		//the only possible invalid input/state
		// tests path into invalid path in set address
		try{
			NodeAddress max = new NodeAddress(Integer.MAX_VALUE);
			max.addOne();
			Assert.fail();
		}catch(IllegalArgumentException e){
		}
		//test the smallest possible address and some other valid addresses
		// tests path not into invalid path in set address
		NodeAddress zero = new NodeAddress(0);
		NodeAddress normal = new NodeAddress(Hundred);
		zero.addOne();
		Assert.assertEquals(Hundred+1, normal.addOne().getAddress());
		Assert.assertEquals(1, zero.addOne().getAddress());
	}
	/**
	 * takes this Address and subtracts one to it then returns the new address
	 * @precondition the NodeAddress this is called on is not at the minimum allowed address
	 * @postcondition returns a new NodeAddres with an address one less than this ones.
	 */
	public NodeAddress decrement(){
		
		return new NodeAddress(address-1);
	}
	/**
	 * tests all possible paths through decrement and the only invalid input;
	 */
	// Equivalence partitions are  0< address <= max or address == 0 
	public void testDecrement(){
		//testing only possible invalid input
		// tests path into invalid path in set address
		try{
			NodeAddress zero = new NodeAddress(0);
			zero.decrement();
			Assert.fail();
		}catch(IllegalArgumentException e){
		}
		// test largest possible valid and some random valid inputs(boundry value)
		// tests path not into invalid path in set address
		NodeAddress max = new NodeAddress(Integer.MAX_VALUE);
		NodeAddress normal = new NodeAddress(Hundred);
		Assert.assertEquals(Hundred-1, normal.decrement().getAddress());
		Assert.assertEquals(Integer.MAX_VALUE-1, max.decrement().getAddress());
	}
	/**
	 * takes in to NodeAddresses and returns the midpoint as a NodeAddress
	 * @param min The Lower NodeAddress
	 * @param max the Upper Node Address
	 * @return the Node address that is in the middle of the two
	 * @precondition true
	 * @postcondition returns the NodeAddress that is the average of the two incoming
	 * addresses rounding down 
	 */
	public static NodeAddress midPoint(NodeAddress min,NodeAddress max){
		int mid = (min.getAddress() + max.getAddress())>>>1;
		return new NodeAddress(mid);
	}
	/**
	 * test midpoint with boundary values, even though they make no difference
	 */
	//Equvalance partion is all values should be the same , but need to check boundries
	// two possible paths except one is unreachable
	public void testMidPoint(){
		// upper boundray case
		NodeAddress max = new NodeAddress(Integer.MAX_VALUE);
		Assert.assertEquals(max,NodeAddress.midPoint(max, max));
		//lower boundray case
		Assert.assertEquals(0,
				NodeAddress.midPoint(new NodeAddress(0), new NodeAddress(1)).address);
	}
	/**
	 * takes in a NodeAddress and returns it's integer representation
	 * @precondition the incoming NodeAddress is not null
	 * @postcondition returns the integer representation of this node Address
	 */
	public static int asInt(NodeAddress nodeAddress) {
		return nodeAddress.getAddress();
	}
	/**
	 * test all paths though as Int(one)(really just a getter)
	 */
	public void testAsInt(){
		//testing largest smallest, and average case states, all are the same only possible path
		NodeAddress max = new NodeAddress(Integer.MAX_VALUE);
		NodeAddress zero = new NodeAddress(0);
		NodeAddress normal = new NodeAddress(Hundred);
		Assert.assertEquals(Integer.MAX_VALUE,NodeAddress.asInt(max));
		Assert.assertEquals(0,NodeAddress.asInt(zero));
		Assert.assertEquals(Hundred,NodeAddress.asInt(normal));
	}
	/**
	 * with an edge pointer it computes the child Node for this Node in that
	 * edgeNodes height 
	 * @precondition the incoming Node address is the address of an edge pointer of this address's
	 * node
	 * @postcondition returns the node address that the child of this nodeAddress would have
	 */
	public NodeAddress getChild(NodeAddress edgePointer){
		Assert.assertTrue(Integer.toBinaryString(address).length()
				< Integer.toBinaryString(edgePointer.address).length());
		return new NodeAddress(getAddress() + Integer.highestOneBit(edgePointer.getAddress()));
	}
	/**
	 * test that the child returned depends on the incoming addresses length
	 */
	// Equvilance partitioning other address is valid or not, only uses Integer methods to make
	// work, so i need to check invalid case were i did the logic
	public void testGetChild(){
		NodeAddress fun = new NodeAddress(Hundred);
		NodeAddress zero = new NodeAddress(0);
		NodeAddress fun2 = new NodeAddress(Hundred>>2);
		//two normal cases, just in the middle of the valid input
		Assert.assertEquals(SIXTY_FOUR, zero.getChild(fun).address);
		Assert.assertEquals(SIXTEEN, zero.getChild(fun2).address);
		//invalid input one, where it is jsut barely invalid, same level of hypeerweb
		try{
			fun.getChild(fun);
			Assert.fail();
		}catch(AssertionError e){
			
		}
		//standard invalid input
		try{
			fun.getChild(fun2);
			Assert.fail();
		}catch(AssertionError e){
			
		}
		//boundray value just barely valid case
		NodeAddress max = new NodeAddress(Integer.MAX_VALUE);
		NodeAddress par = new NodeAddress(max.address - Integer.highestOneBit(max.address));
		Assert.assertEquals(max, par.getChild(max));
	}
	/**
	 * Goes through the given neighbors and finds which ones are on your way to destination
	 * then returns a random one
	 * @precondition destination is the NodeAddress we desire to make it to and neighbors
	 * is a collection of this NodeAddress's neighbors 
	 * @postcondition returns a node pointer to a node that is on the path to the destination, 
	 *   or the nullNode if there is no node on the path to destination
	 * or null if this node is closer than any of it's neighbors
	 */
	public Node onPathTo(NodeAddress destination, Collection<Node> neighbors){
		List<Node> possiblePaths = new ArrayList<Node>();
		//System.out.println("At: " + this + " looking for: " + destination);
		int distanceGetter = getAddress() ^ destination.getAddress();
		int distance = Integer.bitCount(distanceGetter);
		for(Node potential : neighbors){
			if(potential == null){
				continue;
			}
			int tempDistanceGetter = potential.getAddress().getAddress()
				^ destination.getAddress();
			int tempdistance = Integer.bitCount(tempDistanceGetter);
			if(tempdistance == distance - 1){
				possiblePaths.add(potential);
			}
		}
		//Assert.assertTrue(possiblePaths.size() > 0);
		
		Random rand = new Random();
		if(possiblePaths.size()==0){
			return null;
		}
		int spot = rand.nextInt(possiblePaths.size());
		Node retPath = possiblePaths.get(spot);
		return retPath;
	}
	/**
	 * test that this node works for one pass through neighbors,
	 * and no passes through, then tests  large cases, then tests to ensure random paths chosen
	 */
	// three paths through code,  first valid case into the loop and out the normal return
	// second path, no neighbors skips loop and goes into the null return if statement
	// third path, neighbors but none closer than this node, 
	// goes through loop and into null return if
	// Equivalence partitioning 
	public void testOnPathTo(){
		Node two = new Node(2,new NodeAddress(2));
		Node[] input1 = {two};
		Node[] input2 = {};
		NodeAddress zero = new NodeAddress(0);
		NodeAddress six = new NodeAddress(2*2+2);
		//valid one possible case(second path)
		Assert.assertEquals(two, zero.onPathTo(six, 
					Arrays.asList(input1)));
		//invalid case with no neighbors
		//third path
		Assert.assertNull(zero.onPathTo(six,
				Arrays.asList(input2)));
		Connection connect = new Connection();
		for(int i = 0; i < SIXTY_FOUR; i++){
			connect.addNode(i);
		}
		List<Node> nodes = connect.getAllNodes();
		Node[] output = {two, new Node(null,new NodeAddress(2*2))};
		//valid case with several neighbors but only two correct
		//first path
		Assert.assertTrue(Arrays.asList(output).contains(
				nodes.get(0).getAddress().onPathTo(six, nodes.get(0).getNeighbors())));
		//invalid case with many neighbors
		Assert.assertNull(nodes.get(0).getAddress().onPathTo(new NodeAddress(SIXTY_FOUR)
			,nodes.get(SIXTY_FOUR-1).getNeighbors()));
		NodeAddressTest test = new NodeAddressTest();
		//makes sure a random path is delievered from node(not always the same path)
		test.testOnPathToRandom();
	}
	/**
	 *@precondition the incoming object is a NodeAddress
	 *@postcondition returns a positive int if this address is bigger 0 if they are equal or 
	 *negative int if the other address is bigger
	 */
	public int compareTo(NodeAddress o){		
		return getAddress() - o.getAddress();
	}
	/**
	 * @precondition true
	 * @post returns a int that can be used to represent this Object
	 */
	public int hashCode(){
		return getAddress();
	}
	/**
	 * @precondition o is a NodeAddress
	 * @post returns true if the two objects are equal, false in all other cases
	 */
	public boolean equals(Object o){
		return getAddress() == ((NodeAddress)o).getAddress();
	}
	/**
	 * gives a string representation of the binary address and the int address of this NodeAddress
	 */
	public String toString(){
		if(getAddress() == Node.BOGUS-1){
			return "null";
		}
		String result = Integer.toBinaryString(getAddress());
		
		result += " (" + getAddress() + ")";
		return result;
	}
	/**
	 * test that two string properly out puts string
	 */
	//Equvalnse partioning, directly follows equivalence partitioning which are
	//all others, and special case for bogus value, which returns the string "null"
	public void testToString(){
		String expected = "10110 (22)";
		final int address = 22;
		Assert.assertEquals(expected, new NodeAddress(address).toString());
		Assert.assertEquals("null", new NodeAddress(Node.BOGUS-1).toString());
	}
	/**
	 * makes a Node Address with the address
	 *@precondition address is positive
	 *@post returns a new NodeAddress with the given integer value
	 */
	public static NodeAddress toAddress(int address) {
		
		return new NodeAddress(address);
	}
	
	/**
	 * From the parent Node computes what the next youngest Child is
	 * @pre this is a valid child of parentAddress
	 * @post returns the next largest address that could be a child of this Node, or
	 * returns null if there is none
	 */
	public NodeAddress getNextYoungestChild(NodeAddress parentAddress) {
		//int parentLength = Integer.toBinaryString(parentAddress.address).length();
		if((this.address - Integer.highestOneBit(address)) != parentAddress.address){
			throw new IllegalArgumentException(parentAddress +" is not a " +
					"valid parent of " + address);
		}
		//int childLength = Integer.toBinaryString(address).length();
		int childAddress = Integer.highestOneBit(address)/2 + parentAddress.address;
		if(childAddress == parentAddress.address || 
				Integer.highestOneBit(childAddress)==Integer.highestOneBit(address)){
			return null;
		}
		//System.out.println("Parent: " + parentAddress);
		//System.out.println("here: " + this);
		//System.out.println("Child: " + childAddress);

		return new NodeAddress(childAddress);
	}
	/**
	 * computes if this node address has an old fold that we need to be concerned about if the 
	 * removal points address is the incoming address
	 * @pre removalPoint is a valid address of this tree and is most recently added node in a
	 * hypeer web
	 * @post returns true if this node is the fold pointer of another node besides it's fold pointer
	 */
	public boolean hasOldFold(NodeAddress removalPoint){
		NodeAddress oldFold = computeOldFold();
		int minPossible = Integer.highestOneBit(address)*2 + oldFold.address;
		int maxPossible = Integer.highestOneBit(address)*2 + address;
		//System.out.println(address+ " " + minPossible + " " + maxPossible);
		return removalPoint.address > minPossible && removalPoint.address <= maxPossible;
	}
	/**
	 * computesthis node address's old fold's addresss
	 * @pre hasOldFold returns true
	 * @post returns the old fold of this node
	 */
	public NodeAddress computeOldFold(){
		int bits = Integer.toBinaryString(address).length();
		int oldFold = (address ^ (int)Math.pow(2,bits)-1);
		return new NodeAddress(oldFold);
	}
	/**
	 * Calculates the addresses of all possible children based on the maximum
	 * 	address of the node in the hypeerweb
	 * @param maxAddress - the maximum address in the hypeerweb
	 * @pre a valid address is passed
	 * @post returns a list of node addresses of the possible children of the
	 *  node with address provided
	 */
	public List<NodeAddress> getAllPossibleChildren(NodeAddress maxAddress) {
		//System.out.println(maxAddress);
		List<NodeAddress> possible = new ArrayList<NodeAddress>();
		int highBit = Integer.highestOneBit(maxAddress.address);
		while(highBit > Integer.highestOneBit(address)){
			possible.add(new NodeAddress(address+highBit));
			highBit=highBit/2;
		}
		List<NodeAddress> bad = new ArrayList<NodeAddress>();
		for(NodeAddress n : possible){
			if(maxAddress.address <= n.address){
				bad.add(n);
			}
		}
		possible.removeAll(bad);
		return possible;
	}
	
	/**
	 * Checks if neghborAddress is a valid neighbor for the node at this address.
	 * 
	 * @param neighborAddress the neighbor's address
	 * 
	 * @pre neighborAddress is a valid NodeAddress
	 * @post returns true if neighborAddress is a valid neighbor address
	 */
	public boolean isValidNeighbor(NodeAddress neighborAddress) {
		int bitDifference = address ^ neighborAddress.getAddress();
		if (Integer.bitCount(bitDifference) == 1) {
			return true;
		}
		return false;
	}
	/**
	 * test that isValidNeighbor works in the cases, of the same node, valid node
	 * and just one off valid and also way off of valid.
	 */
	//Equivalence partitioning  is valid and invalid input, no other ones
	// two paths into valid if statement and not
	public void testIsValidNeighbor(){
		NodeAddress zero = new NodeAddress(0);
		//test to make sure self case fails(off by one
		Assert.assertFalse(zero.isValidNeighbor(zero));
		NodeAddress one = new NodeAddress(1);
		final int three = 3;
		//test valid case
		Assert.assertTrue(zero.isValidNeighbor(one));
		//test valid case with the two bit being different
		Assert.assertTrue(one.isValidNeighbor(NodeAddress.toAddress(three)));
		//test invalid case off my more than one
		Assert.assertFalse(zero.isValidNeighbor(NodeAddress.toAddress(three).addOne().addOne()));
	}
	/**
	 * Performs a bitwise XOR operation on the addresses
	 * 
	 * @param other the address to XOR with this address
	 * 
	 * @pre other is a valid node address
	 * @post returns a node address which is a bitwise XOR this address and the parameter
	 */
	public NodeAddress XOR(NodeAddress other) {
		return new NodeAddress(address ^ other.getAddress());
	}
	
	/**
	 * Calculates whether the neighbor at the specified address is a "less significant" neighbor, that is, a neighbor
	 *   will have one bit flipped in a less significant (further right) position than 
	 *   the last "1" bit of this address (in binary). *   
	 * 
	 * @param neighborAddress the address to check
	 * 
	 * @pre neighborAddress is the address of a neighbor of this address's node.  
	 * @post returns true if the neighbor is a less significant neighbor, or if this address is zero
	 */
	public boolean isLessSignificantNeighbor(NodeAddress neighborAddress){
		//Assert.assertTrue(isValidNeighbor(neighborAddress)); 
		
		//System.out.println("isLessSignificant called on " + this.address + ", " + neighborAddress.address);
		
		if (address == 0) {
			//System.out.println("returned true");
			return true;
		}
		
		int thisLowBit = Integer.lowestOneBit(address);
		int neighborLowBit = Integer.lowestOneBit(address ^ neighborAddress.getAddress());
		
		if (thisLowBit > neighborLowBit) {
			//System.out.println("returned true");
			return true;
		}	
		//System.out.println("returned false");
		return false;
	}
	public boolean isSmallerBitflipThan(NodeAddress previous, NodeAddress next) {
		int previousFlip = this.getAddress() ^ previous.getAddress();
		int nextFlip = this.getAddress() ^ next.getAddress();
		
		if (previousFlip > nextFlip) {
			return true;
		}
		return false;
	}
}

